|
The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlund credited Curtis and Lyndon as co-discoverers.〔.〕 It has been called "one of the fundamental results in symbolic dynamics".〔.〕 The theorem states that a function from a shift space to itself represents the transition function of a one-dimensional cellular automaton if and only if it is continuous (with respect to the Cantor topology) and equivariant (with respect to the shift map). More generally, it asserts that the morphisms between any two shift spaces (i.e., continuous mappings that commute with the shift) are exactly those mappings which can be defined uniformly by a local rule. The version of the theorem in Hedlund's paper applied only to one-dimensional finite automata, but a generalization to higher dimensional integer lattices was soon afterwards published by ,〔.〕 and it can be even further generalized from lattices to discrete groups. One important consequence of the theorem is that, for reversible cellular automata, the reverse dynamics of the automaton can also be described by a cellular automaton. ==Definitions== An alphabet is any finite set of symbols, which may be thought of as the states of the cells in a cellular automaton. A ''configuration'' is a bi-infinite sequence of symbols from the alphabet: :. A ''position'' in a configuration is an integer, the index of one of the symbols in the sequence; the positions may be thought of as the cells of a cellular automaton. A ''pattern'' is a finite set of positions and an assignment of symbols to each of these positions. The shift space is the set of all possible configurations over a given alphabet. It may be given the structure of a topological space according to the Cantor topology, in which the fundamental open sets are the sets of configurations that match any single pattern and the open sets are arbitrary unions of fundamental open sets. In this topology, a function from configurations to configurations is continuous if, for any fixed pattern defining a fundamental open set , the set of configurations mapped by into can itself be described by a (possibly infinite) set of patterns, with the property that a configuration belongs to if and only if it matches a pattern in . The shift map is a particular continuous function on the shift space that transforms a configuration into a new configuration in which each symbol is shifted one position over from its previous position: that is, for every integer , . A function is equivariant under the shift map if the transformation on configurations described by commutes with the shift map; that is, for every configuration , it must be the case that . Intuitively, this means that every position of the configuration is updated by using the same rule as every other position. A cellular automaton is defined by a rule for computing the new value of each position in a configuration based only on the values of cells in a finite neighborhood surrounding the position, with all positions of the configuration being updated simultaneously based on the same update rule. That is, the new value of a position is a function only of the values of the cells in its neighborhood rather than depending more generally on an unbounded number of cells of the previous configuration. The function that uses this rule to map a configuration of the cellular automaton into its successor configuration is necessarily equivariant with respect to the shift map, by the assumption that all positions use the same update rule. It is also necessarily continuous in the Cantor topology: if is a fixed pattern, defining a fundamental open set , then is defined by a finite set of patterns, the assignments to cells in the neighborhood of that cause to produce . The Curtis–Hedlund–Lyndon theorem states that these two properties are sufficient to define cellular automata: every continuous equivariant function is the update rule of a cellular automaton. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Curtis–Hedlund–Lyndon theorem」の詳細全文を読む スポンサード リンク
|